﻿/*
题目: 一个小组的最大实力值

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。

请你返回老师创建的小组能得到的最大实力值为多少。

https://leetcode.cn/problems/maximum-strength-of-a-group/?envType=daily-question&envId=2024-09-03
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 属于《乘积最大子数组》的升级版 => 子序列版
    using LL = long long;

    long long maxStrength(vector<int>& nums) {
        vector<LL> maxf(nums.size(), 0);
        vector<LL> minf(nums.size(), 0);
        minf[0] = maxf[0] = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                // 可以选择 不选，选（基于历史最大），选（基于历史最小），或者当前就是最大的
                maxf[i] = max({ maxf[i - 1], maxf[i - 1] * nums[i], minf[i - 1] * nums[i], (long long)nums[i] });
                minf[i] = min({ minf[i - 1], minf[i - 1] * nums[i], maxf[i - 1] * nums[i], (long long)nums[i] });
            }
        }

        return maxf[nums.size() - 1];
    }
};
